from typing import *
from bisect import bisect_left


class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:

        n, q = len(nums), len(queries)

        def f(k):
            dp = [0] * (n + 1)
            for i in range(k):
                l, r, v = queries[i]
                dp[l] += v
                dp[r + 1] -= v
            tot = 0
            for i, v in enumerate(nums):
                tot += dp[i]
                if tot < v:
                    return False
            return True

        i = bisect_left(range(q + 1), True, key=f)

        return i if i <= q else -1


[2, 0, 2]
[[0, 2, 1], [0, 2, 1], [1, 1, 3]]
[4, 3, 2, 1]
[[1, 3, 2], [0, 2, 1]]
